/**
 * 二叉搜索树
 * 一个节点就是一个对象，对象中包含了三个属性：key、left、right
 * key：节点的值，用于比较大小
 * left：指向左子树的指针
 * right：指向右子树的指针
 * 二叉搜索树的特点：
 * 1. 左子树上所有节点的值均小于它的根节点的值
 * 2. 右子树上所有节点的值均大于它的根节点的值
 * 3. 以此类推：左、右子树也分别为二叉查找树
 * 4. 没有键值相等的节点
 * 5. 二叉搜索树的中序遍历是升序排列
 * 6. 二叉搜索树的查找、插入、删除的时间复杂度都是 O(logn)
 */
class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(key) {
    this.root = insertNode(this.root, key);
  }

  search(key) {
    return searchNode(this.root, key);
  }

//   中序遍历
  inOrderTraverse(callback) {
    inOrderTraverseNode(this.root, callback);
  }


}

// 创建树节点
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

// 插入节点
function insertNode(node, key) {
  if (node === null) {
    node = new Node(key);
  } else if (key < node.key) {
    node.left = insertNode(node.left, key);
  } else {
    node.right = insertNode(node.right, key);
  }
  return node;
}

// 查找节点,存在返回true，不存在返回false
function searchNode(node, key) {
  if (node === null) {
    return false;
  }
  if (key < node.key) {
    return searchNode(node.left, key);
  } else if (key > node.key) {
    return searchNode(node.right, key);
  } else {
    return true;
  }
}

const tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);

console.log(tree)
console.log(tree.search(1)); // false

// 中序遍历
function inOrderTraverseNode(node, callback) {
  if (node !== null) {
    inOrderTraverseNode(node.left, callback);
    callback(node.key);
    inOrderTraverseNode(node.right, callback);
  }
}

tree.inOrderTraverse((key) => {
  console.log(key);
})

// 3 5 7 8 9 10 11 12 13 14 15 18 20 25
